#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/4 21:40
# @USER    : Shengji He
# @File    : 4Sum.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        """
        Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums
        such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

        Note:

        The solution set must not contain duplicate quadruplets.

        Example:
            Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

            A solution set is:

            [
              [-1,  0, 0, 1],

              [-2, -1, 1, 2],

              [-2,  0, 0, 2]
            ]


        :param nums: List[int]
        :param target: int
        :return: List[List[int]]
        """
        ans = []
        nums.sort()
        for i in range(len(nums) - 3):
            if (0 <= target < nums[i]) or (target < 0 and nums[i] * 4 > target):
                return ans
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, len(nums) - 2):
                if (0 <= target < nums[j] + nums[i]) or (target < min([0, nums[i] + nums[j] * 3])):
                    break
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                s, e = j + 1, len(nums) - 1
                while s < e:
                    if nums[i] + nums[j] + nums[s] + nums[e] == target:
                        ans.append([nums[i], nums[j], nums[s], nums[e]])
                        while s < e and nums[s] == nums[s + 1]:
                            s += 1
                        while s < e and nums[e] == nums[e - 1]:
                            e -= 1
                        s += 1
                        e -= 1
                    elif (nums[i] + nums[j] + nums[s] + nums[e]) > target:
                        while s < e and nums[e] == nums[e - 1]:
                            e -= 1
                        e -= 1
                    else:
                        while s < e and nums[s] == nums[s + 1]:
                            s += 1
                        s += 1
        return ans


if __name__ == '__main__':
    S = Solution()
    # nums = [1, 0, -1, 0, -2, 2]
    # target = 0
    nums = [1, -2, -5, -4, -3, 3, 3, 5]
    target = -11
    print(S.fourSum(nums, target))
    print('done')
